package com.zzh.utils;

/**
 * @ClassName arithmeticUtils
 * @date 2021/4/15 10:29
 * @Version 1.0
 * @Description //算法工具类
 * @USER root
 */
public class arithmeticUtils {

    //回文数
    public static boolean isPalindromeOneMethod(int x) {
        if (x < 0) {
            return false;
        }
        char[] ch = String.valueOf(x).toCharArray();
        if (ch.length == 1) {
            return true;
        } else if (ch.length >= 2){
            for (int i = 0; i < ch.length/2; i++) {
                if (ch[i] != ch[ch.length - i - 1]) {
                    return false;
                }
            }
        }
        return true;
    }

    //回文数
    public static boolean isPalindromeTwoMethod(int x) {
        if (x < 0) {
            return false;
        }
        StringBuffer stringBuffer = new StringBuffer(x);
        if (stringBuffer.length() == 1) {
            return true;
        } else if (stringBuffer.length() >=2) {
            StringBuffer reverse = stringBuffer.reverse();
            if (!reverse.equals(stringBuffer)) {
                return false;
            }
        }
       return true;
    }

    //折半查找
    public static int binsearch(int[] a,int value,int low,int hight) {
        int mid = low + (low + hight) /2;
        if (a[mid] == value) {
            return a[mid];
        }
        if (a[mid] > value) {
            return binsearch(a,value,low,mid-1);
        }
        if (a[mid] < value) {
            return binsearch(a,value,mid-1,hight);
        }
        return -1;
    }
    //冒泡
    public static void bullsort(int[] numbers ) {
        int temp = 0;
        int size = numbers.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size-1-i; j++) {
                if(numbers[j] > numbers[j+1])  //交换两数位置
                {
                    temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
                }
            }
        }
    }


    //快排
    public static int getMiddle(int[] numbers ,int low ,int hight) {
        int temp = numbers[low];
        while (low < hight) {
            while (low < hight && numbers[hight] >= temp) {
                hight--;
            }
            numbers[low] = numbers[hight];
            while (low < hight && numbers[hight] < temp) {
                low++;
            }
            numbers[hight] = numbers[low];
        }
        numbers[low] = temp;
        return low;
    }

    public static void quicksort(int[] numbers ,int low,int hight) {
        if (low < hight) {
            int middle = getMiddle(numbers,low,hight);
            quicksort(numbers,low,middle-1);
            quicksort(numbers,middle+1,hight);
        }
    }

    //选择排序
    public static void selector(int[] numbers){
        int size  = numbers.length;
        int temp = 0;
        for (int i = 0; i < size; i++) {
            int k = i;
            for (int j = size-1; j > i ; j++) {
                if (numbers[j] < numbers[k]) {
                    k = j;
                }
            }
            temp = numbers[i];
            numbers[i] = numbers[k];
            numbers[k] = temp;
        }
    }
    //插入排序
    public static void insertSort(int[] numbers) {
        int size = numbers.length;
        int temp = 0;
        int j = 0;
        for (int i = 0; i < size; i++) {
            temp = numbers[i];
            for (j = i;j > 0&& temp < numbers[j-1];j--) {
                numbers[j] = numbers[j-1];
            }
            numbers[j] = temp;
        }
    }

    public static int[] sort(int[] nums ,int low ,int hight) {
        int mid = (low + hight ) /2 ;
        if (low < hight ) {
            sort(nums,low,mid);
            sort(nums,mid + 1,hight);
            marge(nums,low,mid,hight);
        }
        return nums;
    }

    private static void marge(int[] nums, int low, int mid, int hight) {
        int[] temp = new int[hight - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= hight) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= hight) {
            temp[k++] = nums[j++];
        }
        for (int k2 = 0;k2 < temp.length;k2 ++) {
            nums[k2 + low] = temp[k2];
        }
    }



    

}
